package easy;

/**
 * 2908. 元素和最小的山形三元组 I
 * 创建时间：2024-03-29 11:27
 */
public class 元素和最小的山形三元组I_2980 {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minimumSum(new int[]{8,6,1,5,3}));
    }

    static class Solution {
        public int minimumSum(int[] nums) {
            int n = nums.length;
            int[] pre = new int[n];
            int[] suf = new int[n];
            int ans = Integer.MAX_VALUE;
            pre[0] = nums[0];
            suf[n-1] = nums[n-1];
            for (int i = 1; i < n; i++) {
                pre[i] = Math.min(pre[i - 1], nums[i]); // [0, i]
                suf[n - i - 1] = Math.min(suf[n - i], nums[n - i - 1]); // [i, n-1]
            }

            for (int i = 1; i < n - 1; i++) {
                if (pre[i - 1] < nums[i] && nums[i] > suf[i + 1]) {
                    ans = Math.min(ans, pre[i - 1] + nums[i] + suf[i + 1]);
                }
            }
            return ans == Integer.MAX_VALUE ? -1 : ans;
        }
    }
}
